/* 
 * File:   euler.cpp
 * Author: Trunghpb
 * Created on March 18, 2010, 11:22 AM
 *
 * Cho đồ thị vô hướng liên thông
 * INPUT:
 * N là số cạnh
 * N dòng tiếp mỗi dòng ghi 2 số là đỉnh đầu và cuối của một cạnh
 *
 * OUTPUT:
 * Dòng đầu trả lời:
 * Đồ thị có là đồ thị euler không.
 * Đồ thị nửa euler.
 * Đồ thị liên thông.
 */

#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

int     N, M, socanh, sodinh, loai_dothi, dstart;
int     a[MAX][MAX];
int     luudinh[MAX],
        bacdinh[MAX],
        chuaxet[MAX];

void init_chuaxet(){
	for(int i = 0; i<N;i++){
		chuaxet[i] = 0;
	}
}
void dem_bac(){
    for(int i = 0; i<N; i++){
        for(int j=0; j<N; j++){
            bacdinh[i] += a[i][j];
        }
    }
}

int test_euler(){
    for(int i = 0; i<N; i++){
        if (bacdinh[i] % 2 != 0) return FALSE;
    }
    return TRUE;
}

int test_sermi_euler(){
    int sole = 0;
    for(int i=0; i<N; i++){
        if (bacdinh[i]%2 != 0){
            sole++;
            dstart = i;
            if (sole>2) return FALSE;
        }
    }
    if (sole == 2) return TRUE;
    return FALSE;
}

void dfs(int u){
    for(int v = 0; v<N; v++){
        if (chuaxet[v] && a[u][v]){
            chuaxet[v] = FALSE;
            sodinh++;
            luudinh[sodinh] = v;
            dfs(v);
        }
    }
}

void tim_euler(){
    int stack[MAX];
    int top, u, v;
    top = 0; stack[top] = 0;
    do{
        u = stack[top];
        v = 0;
        while (v < N && a[u][v] == 0) v++;

        if (v >= N){
            luudinh[sodinh++] = u;
            top--;
        }else{
            top++;
            stack[top] = v;
            a[u][v] = 0;
            a[v][u] = 0;
        }

    }while (top > 0);
}

void tim_sermi_euler(int start){
    int stack[MAX];
    int top, u, v;
    top = 0; stack[0] = start;
	sodinh=0;
    do{
        u = stack[top];
        v = 0;
        while (v<N && a[u][v]==0) v++;
        if (v>=N){
            luudinh[sodinh++] = u;
            top--;
        }else{
            top++;
            stack[top] = v;
            a[u][v] = 0;
            a[v][u] = 0;
        }
    }while (top >= 0);
}

void tim_lien_thong(){
	init_chuaxet();
	sodinh=0;
    dfs(0); // dfs tai dinh 1
}

void init(){
    socanh = 0; sodinh = 0;
    for(int i=0; i<N; i++) luudinh[i] = 0;
}
void init_a(){
    for(int i = 0; i<MAX; i++){
        bacdinh[i] = 0;
        for(int j=0; j<MAX; j++){
            a[i][j] = 0;
        }
    }
}

void input(){
    init_a();
    FILE *fi;
    int u, v;
    fi = fopen("data.in","r");
    fscanf(fi, "%d %d\n", &N, &M);
    for(int i=0; i<M; i++){
        fscanf(fi,"%d %d", &u, &v);
        a[u-1][v-1] = 1;
        a[v-1][u-1] = 1;
    }
    fclose(fi);
}

void xuli(){
    init();
    dem_bac();

    if (test_euler()){
        tim_euler();
        loai_dothi = 1;
    }else if (test_sermi_euler()){
        tim_sermi_euler(dstart);
        loai_dothi = 2;
    }else{
        tim_lien_thong();
        loai_dothi = 3;
    }
}

void output(){
    if (sodinh<N){
        // vo nghiem
        printf("Khong lien thong\n");
    }else{
        // in ra ket qua tra ve + duong di
        switch(loai_dothi){
            case 1:
                printf("Do thi euler\n");
				// in danh sach duong di - chu trinh
				for(int i=0; i<sodinh; i++){
					printf("%d - ", luudinh[i]+1);
				}
				printf("%d", luudinh[0]+1); // tro lai dinh bat dau
                break;
            case 2:
                printf("Do thi sermi-euler\n");
				for(int i=0; i<sodinh-1; i++){
					printf("%d - ", luudinh[i]+1);
				}
				printf("%d", luudinh[sodinh -1]+1); // tro lai dinh bat dau
                break;
            case 3:
               
                break;
            default:
                break;
        }
        getch();
    }
}
/*
 * 
 */
int main(int argc, char** argv) {
    input();
    xuli();
    output();
    return 0;
}

